As the demand for high throughput wireless communication grows, the importance of high spectrum efficiency is increasing. A Multiple-Input-Multiple-Output (MIMO) system has a plurality of antennas disposed at both the transmitter and the receiver sides. Thus, transmission rate can be increased by simultaneously transmitting multiple data streams within one frequency band. However, multiple data streams may interfere with each other at the receiver side. Thus, signal separation and detection techniques are required for decoupling.
Maximum likelihood detection (MLD) is a prevailing algorithm used to search among all possible transmitted symbol vectors at a receiver side to obtain a solution most resembling the transmitted one. FIG. 1 shows a conventional search tree in which a plurality of search paths is presented. Assuming there are four symbols transmitted by four transmit antennas at the transmitter side, the search process is performed within a search tree comprising four layers L4 to L1, wherein each layer corresponds to one specific transmit antenna. If 64QAM (Quadrature Amplitude Modulation) is adopted for each symbol, there would be 64 possible nodes P1 to P64 to be searched at each layer. As shown in FIG. 1, there are a total of 644 combinations for four layers to be examined, which is inefficient for practical implementation.
Thus, to decrease algorithmic complexity, a sphere decoding (SD) algorithm has been proposed. An upper limit of a cost function is employed to effectively restrict the search range of an optimal path by excluding unnecessary combinations. The upper limit value, r2, is conventionally referred to as the radius of a sphere. During each search step, every path 110 connecting one node to another node residing at the next layer causes a corresponding Euclidean Distance Increment (EDI), wherein an accumulation of the EDIs from the top layer to the current layer is referred to as a Partial Euclidean Distance (PED) of the partial search path. The PED is then compared with the sphere radius r2 to determine the validity of the partial search result. When the search process reaches the bottom layer of the search tree, a Euclidean distance (ED) of a complete search path is then obtained.
Meanwhile, according to the Schnorr-Euchner (SE) algorithm, when the search proceeds to the mth layer, a node closest to the sphere center at a specific layer will be first examined. The algorithmic principle is to examine a node of a smaller EDI with a higher priority, by which the average time to obtain an optimal result can be shortened because the radius of the sphere will shrink more quickly. Furthermore, another algorithm, a Fixed-Complexity Sphere Decoding algorithm, to decrease algorithmic complexity has been proposed to employ a modified V-BLAST sorting algorithm to rearrange the search trees such that a full search scheme is adopted over several top layers, wherein a single direction search scheme is performed over the other layers to achieve a near optimal solution. The V-BLAST sorting algorithm, however, requires significant computation power, thus it is inefficient for mobile systems where frequent sorting is required to account for time-varying channels.